/*
 *  linux/mm/bootmem.c
 *
 *  Copyright (C) 1999 Ingo Molnar
 *  Discontiguous memory support, Kanoj Sarcar, SGI, Nov 1999
 *
 *  simple boot-time physical memory area allocator and
 *  free memory collector. It's used to deal with reserved
 *  system memory and memory holes as well.
 */
// #include <linux/init.h>
// #include <linux/pfn.h>
// #include <linux/bootmem.h>
// #include <linux/module.h>

// #include <asm/bug.h>
// #include <asm/io.h>
// #include <asm/processor.h>

// #include "internal.h"
#include "page_32.h"
#include "bootmem.h"
#include "io_32.h"
#include<strings.h>
#include"kernel.h"
#include <stdio.h>
#include "pfn.h"
#include "bitops_64.h"


#define BUG()
#define likely(x)	__builtin_expect(!!(x), 1)
#define unlikely(x)	__builtin_expect(!!(x), 0)

#define BITS_PER_LONG __WORDSIZE

/*
 * Access to this subsystem has to be serialized externally. (this is
 * true for the boot process anyway)
 */
/* 低端内存(如果地址空间按3∶1划分,通常≤896 MiB)(ZONE_NORMAL和ZONE_DMA)中最大的页号 */
//指定了物理内存数量小于896 MiB的系统上内存页的数目。该值的上界受限于896 MiB可容纳的最大页数（具体的计算在find_max_low_pfn给出）
unsigned long max_low_pfn;
//低端内存最小页号
unsigned long min_low_pfn;
//内存最大页号,可能为低端内存+高端内存
unsigned long max_pfn;

/* 内存管理初始化之前用于管理内存的结构, bootmem 分配器结构定义 */
static bootmem_data_t contig_bootmem_data;
/* 系统内存节点管理结构(同样用于UMA和NUMA系统) */
struct pglist_data contig_page_data = { .bdata = &contig_bootmem_data };

//bootmem 分配器表头,元素为 bootmem_data_t->list,内存不连续的系统可能需要多个bootmem分配器。一个典型的例子是NUMA计算机，其中每个结点注册了一个bootmem分配器，但如果物理地址空间中散布着空洞，也可以为每个连续内存区注册一个bootmem分配器。注册新的自举分配器可使用init_bootmem_core
static LIST_HEAD(bdata_list);
#ifdef CONFIG_CRASH_DUMP
/*
 * If we have booted due to a crash, max_pfn will be a very low value. We need
 * to know the amount of memory that the previous kernel used.
 */
unsigned long saved_max_pfn;
#endif

/* return the number of _pages_ that will be allocated for the boot bitmap */
unsigned long bootmem_bootmap_pages(unsigned long pages)
{
	unsigned long mapsize;

	mapsize = (pages+7)/8;
	mapsize = (mapsize + ~PAGE_MASK) & PAGE_MASK;
	mapsize >>= PAGE_SHIFT;

	return mapsize;
}

/*
 * link bdata in order
 */
//按顺序将 bootmem 分配器加入全局链表 bdata_list
static void link_bootmem(bootmem_data_t *bdata)
{
	bootmem_data_t *ent;

	//如果全局链表头为空加入链表头
	if (list_empty(&bdata_list)) {
		//将 bootmem 分配器加入全局链表 bdata_list
		list_add(&bdata->list, &bdata_list);
		return;
	}
	/* insert in order */
	//全局链表头不为空根据地址大小插入链表
	list_for_each_entry(ent, &bdata_list, list) {
		if (bdata->node_boot_start < ent->node_boot_start) {
			list_add_tail(&bdata->list, &ent->list);
			return;
		}
	}
	//插入链表尾部
	list_add_tail(&bdata->list, &bdata_list);
}

/*
 * Given an initialised bdata, it returns the size of the boot bitmap
 */
//计算bootmem管理的总页数，即页管理位图占的大小
static unsigned long get_mapsize(bootmem_data_t *bdata)
{
	unsigned long mapsize;
	//将bootmem分配器管理的起始物理地址转为页号
	unsigned long start = PFN_DOWN(bdata->node_boot_start);
	unsigned long end = bdata->node_low_pfn;

	//大小按8页对齐(补充，这里按8页对齐是为了调用者的操作——操作的是字节位图，一个字节8位，见后一个函数)
	//一个字节8位，1位表示1页
	mapsize = ((end - start) + 7) / 8;
	//按long类型对齐
	return ALIGN(mapsize, sizeof(long));
}

/*
 * Called once to set up the allocator itself.
 */
/*初始化 bootmem 分配器并加入全局链表 bdata_list
pgdat:内存节点
mapstart:指明位图所占的开始页号。
start和end:指明该分配器所要管理的物理内存的起止页号。
*/
static unsigned long init_bootmem_core(pg_data_t *pgdat,
	unsigned long mapstart, unsigned long start, unsigned long end)
{
	/* IA-32中指向 contig_bootmem_data 全局变量 */
	bootmem_data_t *bdata = pgdat->bdata;
	unsigned long mapsize;

	// 给位图分配内存，PFN_PHYS(mapstart)将页数转为物理地址,phys_to_virt 将物理地址转为虚拟地址，位图占用的内存是从bootmem分配器开始地址开始的一段内存
	bdata->node_bootmem_map = phys_to_virt(PFN_PHYS(mapstart));
	bdata->node_boot_start = PFN_PHYS(start);
	bdata->node_low_pfn = end;
	//按顺序将 bootmem 分配器 bdata 加入全局链表 bdata_list
	link_bootmem(bdata);

	/*
	 * Initially all pages are reserved - setup_arch() has to
	 * register free RAM areas explicitly.
	 */
	//计算存储分配位图大小
	mapsize = get_mapsize(bdata);
	//根据存储分配位图大小初始化位图,全写1，标记该区域内存被占用
	memset(bdata->node_bootmem_map, 0xff, mapsize);

	return mapsize;
}

/*
 * Marks a particular physical memory range as unallocatable. Usable RAM
 * might be used for boot-time allocations - or it might get added
 * to the free page pool later on.
 */
static void reserve_bootmem_core(bootmem_data_t *bdata, unsigned long addr,
					unsigned long size)
{
	unsigned long sidx, eidx;
	unsigned long i;

	/*
	 * round up, partially reserved pages are considered
	 * fully reserved.
	 */
	BUG_ON(!size);
	BUG_ON(PFN_DOWN(addr) >= bdata->node_low_pfn);
	BUG_ON(PFN_UP(addr + size) > bdata->node_low_pfn);

	sidx = PFN_DOWN(addr - bdata->node_boot_start);
	eidx = PFN_UP(addr + size - bdata->node_boot_start);

	for (i = sidx; i < eidx; i++)
		if (test_and_set_bit(i, bdata->node_bootmem_map)) {
#ifdef CONFIG_DEBUG_BOOTMEM
			printk("hm, page %08lx reserved twice.\n", i*PAGE_SIZE);
#endif
		}
}

//页位图设为未使用，下次开始分配内存的地址设为释放的地址
static void free_bootmem_core(bootmem_data_t *bdata, unsigned long addr,
				     unsigned long size)
{
	unsigned long sidx, eidx;
	unsigned long i;

	/*
	 * round down end of usable mem, partially free pages are
	 * considered reserved.
	 */
	BUG_ON(!size);
	BUG_ON(PFN_DOWN(addr + size) > bdata->node_low_pfn);

	if (addr < bdata->last_success)
		bdata->last_success = addr;

	/*
	 * Round up the beginning of the address.
	 */
	//计算要释放的起始地址页号的偏移
	sidx = PFN_UP(addr) - PFN_DOWN(bdata->node_boot_start);
	//计算要释放的结束地址页号的偏移
	eidx = PFN_DOWN(addr + size - bdata->node_boot_start);

	//遍历要释放的页号
	for (i = sidx; i < eidx; i++) {
		/* 位图中对应的项设置为0,完成页的释放 */
		if (unlikely(!test_and_clear_bit(i, bdata->node_bootmem_map)))
			BUG();
	}
}

/*
 * We 'merge' subsequent allocations to save space. We might 'lose'
 * some fraction of a page if allocations cannot be satisfied due to
 * size constraints on boxes where there is physical RAM space
 * fragmentation - in these cases (mostly large memory boxes) this
 * is not a problem.
 *
 * On low memory boxes we get it right in 100% of the cases.
 *
 * alignment has to be a power of 2 value.
 *
 * NOTE:  This function is _not_ reentrant.
 */
//不仅能够分配整个内存页，还能分配页的一部分
void * 
__alloc_bootmem_core(struct bootmem_data *bdata, unsigned long size,
	      unsigned long align, unsigned long goal, unsigned long limit)
{
	unsigned long offset, remaining_size, areasize, preferred;
	unsigned long i, start = 0, incr, eidx, end_pfn;
	void *ret;

	if (!size) {
		printk("__alloc_bootmem_core(): zero-sized request\n");
		BUG();
	}
	BUG_ON(align & (align-1));

	if (limit && bdata->node_boot_start >= limit)
		return NULL;

	/* on nodes without memory - bootmem_map is NULL */
	if (!bdata->node_bootmem_map)
		return NULL;

	//获取bootmem分配器最后一页页号
	end_pfn = bdata->node_low_pfn;
	//将申请内存的限制结束地址转为页号
	limit = PFN_DOWN(limit);
	if (limit && end_pfn > limit)
		end_pfn = limit;

	//计算分配器的总页数
	eidx = end_pfn - PFN_DOWN(bdata->node_boot_start);
	offset = 0;
	//计算分配器开始地址的偏移页数
	if (align && (bdata->node_boot_start & (align - 1UL)) != 0)
		offset = align - (bdata->node_boot_start & (align - 1UL));
	offset = PFN_DOWN(offset);

	/*
	 * We try to allocate bootmem pages above 'goal'
	 * first, then we try to allocate lower pages.
	 */
	//判断开始查找的地址合法
	if (goal && goal >= bdata->node_boot_start && PFN_DOWN(goal) < end_pfn) {
		//计算开始查找的偏移地址，即偏移
		preferred = goal - bdata->node_boot_start;

		//如果开始查找的偏移地址超过了上一次分配成功的偏移地址，则使用上一次分配成功的偏移地址
		if (bdata->last_success >= preferred)
			if (!limit || (limit && limit > bdata->last_success))
				preferred = bdata->last_success;
	} else
		preferred = 0;

	//将开始查找的偏移地址计算成页数
	preferred = PFN_DOWN(ALIGN(preferred, align)) + offset;
	//计算要分配的内存页数，向上进位计算
	areasize = (size + PAGE_SIZE-1) / PAGE_SIZE;
	//步进，将页对齐计算为页数，默认为1
	incr = align >> PAGE_SHIFT ? : 1;

restart_scan:
	//从goal开始，扫描位图，查找满足分配请求的空闲内存区
	for (i = preferred; i < eidx; i += incr) {
		unsigned long j;
		//查询位图所在的地址中，从第偏移位offset位开始，第一个不为0的位的位数(最低位从0开始)，最大值为sizeof(unsigned long)*8 - 1
		i = find_next_zero_bit(bdata->node_bootmem_map, eidx, i);
		i = ALIGN(i, incr);
		if (i >= eidx)
			break;
		if (test_bit(i, bdata->node_bootmem_map))
			continue;
		for (j = i + 1; j < i + areasize; ++j) {
			if (j >= eidx)
				goto fail_block;
			if (test_bit(j, bdata->node_bootmem_map))
				goto fail_block;
		}
		//记录找到的位置
		start = i;
		goto found;
	fail_block:
		i = ALIGN(j, incr);
	}

	if (preferred > offset) {
		preferred = offset;
		goto restart_scan;
	}
	return NULL;

found:
	//将找到的位图位置计算成物理地址保存到分配器中
	bdata->last_success = PFN_PHYS(start);
	BUG_ON(start >= eidx);

	/*
	 * Is the next page of the previous allocation-end the start
	 * of this allocation's buffer? If yes then we can 'merge'
	 * the previous partial page with this allocation.
	 */
	//如果目标页紧接着上一次分配的页，即bootmem_data-> last_pos，内核会检查bootmem_data->last_offset，判断所需的内存（包括对齐数据所需的空间）是否能够在上一页分配或从上一页开始分配
	if (align < PAGE_SIZE &&
	    bdata->last_offset && bdata->last_pos+1 == start) {
		offset = ALIGN(bdata->last_offset, align);
		BUG_ON(offset > PAGE_SIZE);
		//计算上一页可用内存的剩余大小
		remaining_size = PAGE_SIZE - offset;
		//如果要分配的内存小于上一页可用内存的剩余大小，则用上一页可用内存的剩余大小分配内存
		if (size < remaining_size) {
			areasize = 0;
			/* last_pos unchanged */
			//上一次分配的页编号没变，计算新的页内偏移位置
			bdata->last_offset = offset + size;
			//计算出符合分配要求的内存开始地址转为虚拟内存地址返回给调用者
			ret = phys_to_virt(bdata->last_pos * PAGE_SIZE +
					   offset +
					   bdata->node_boot_start);
		} else {
			//计算超出上一页的部分
			remaining_size = size - remaining_size;
			//根据超出部分按页向上进位，计算要分配的页数
			areasize = (remaining_size + PAGE_SIZE-1) / PAGE_SIZE;
			//计算出符合分配要求的内存开始地址转为虚拟内存地址返回给调用者
			ret = phys_to_virt(bdata->last_pos * PAGE_SIZE +
					   offset +
					   bdata->node_boot_start);
			//最后一页的数目保存在 bootmem_data->last_pos
			bdata->last_pos = start + areasize - 1;
			//如果该页未完全分配，则相应的偏移量保存在bootmem_data->last_offset
			bdata->last_offset = remaining_size;
		}
		bdata->last_offset &= ~PAGE_MASK;
	} else {//从新的页开始分配内存
		bdata->last_pos = start + areasize - 1;
		bdata->last_offset = size & ~PAGE_MASK;
		ret = phys_to_virt(start * PAGE_SIZE + bdata->node_boot_start);
	}

	/*
	 * Reserve the area now:
	 */
	//将所有分配出去的页对应的位图置为已使用
	for (i = start; i < start + areasize; i++)
		//新分配的页在位图对应的比特位设置为1
		if (unlikely(test_and_set_bit(i, bdata->node_bootmem_map)))
			BUG();
	//初始化分配出去的内存
	memset(ret, 0, size);
	//将分配成功的内存虚拟地址返回
	return ret;
}
#if 0
static unsigned long free_all_bootmem_core(pg_data_t *pgdat)
{
	struct page *page;
	unsigned long pfn;
	bootmem_data_t *bdata = pgdat->bdata;
	unsigned long i, count, total = 0;
	unsigned long idx;
	unsigned long *map; 
	int gofast = 0;

	BUG_ON(!bdata->node_bootmem_map);

	count = 0;
	/* first extant page of the node */
	//bootmem分配器开始地址的页号
	pfn = PFN_DOWN(bdata->node_boot_start);
	//bootmem分配器使用的总页数
	idx = bdata->node_low_pfn - pfn;
	// 页管理位图
	map = bdata->node_bootmem_map;
	/* Check physaddr is O(LOG2(BITS_PER_LONG)) page aligned */
	if (bdata->node_boot_start == 0 ||
	    ffs(bdata->node_boot_start) - PAGE_SHIFT > ffs(BITS_PER_LONG))
		gofast = 1;
	//遍历bootmem分配器每一页
	for (i = 0; i < idx; ) {
		// 将i处开始的BITS_PER_LONG个bit值全部取反，全1说明位图中的页全没使用
		unsigned long v = ~map[i / BITS_PER_LONG];

		// 释放页时是否一次释放多页
		if (gofast && v == ~0UL) {
			int order;

			//用页号找到对应page结构体的位置
			page = pfn_to_page(pfn);
			count += BITS_PER_LONG;
			//计算阶数
			order = ffs(BITS_PER_LONG) - 1;
			/* 伙伴系统的接口,该函数对每个空闲页调用。该函数内部依赖于标准函数 __free_page 。
			 * 它使得这些页并入伙伴系统（buddy）的数据结构,在其中作为空闲页管理,可用于分配
			 * */
			__free_pages_bootmem(page, order);
			i += BITS_PER_LONG;
			page += BITS_PER_LONG;
		} else if (v) {//每次释放一页
			unsigned long m;

			page = pfn_to_page(pfn);
			for (m = 1; m && i < idx; m<<=1, page++, i++) {
				if (v & m) {
					count++;
					__free_pages_bootmem(page, 0);
				}
			}
		} else {
			i += BITS_PER_LONG;
		}
		pfn += BITS_PER_LONG;
	}
	total += count;

	/*
	 * Now free the allocator bitmap itself, it's not
	 * needed anymore:
	 */
	//释放位图占用的内存到伙伴系统中

	// 获得物理内存区域bitmap对应的struct page
	page = virt_to_page(bdata->node_bootmem_map);
	count = 0;
	// 计算当前物理内存区域对应的bitmap占用的物理内存页的数量
	idx = (get_mapsize(bdata) + PAGE_SIZE-1) >> PAGE_SHIFT;
	// 将bitmap占用的物理页转移到buddy分配器中
	for (i = 0; i < idx; i++, page++) {
		__free_pages_bootmem(page, 0);
		count++;
	}
	total += count;
	bdata->node_bootmem_map = NULL;

	// 返回释放物理页的数量
	return total;
}
#else
static unsigned long free_all_bootmem_core(pg_data_t *pgdat){

}
#endif
unsigned long init_bootmem_node(pg_data_t *pgdat, unsigned long freepfn,
				unsigned long startpfn, unsigned long endpfn)
{
	return init_bootmem_core(pgdat, freepfn, startpfn, endpfn);
}

void reserve_bootmem_node(pg_data_t *pgdat, unsigned long physaddr,
				 unsigned long size)
{
	reserve_bootmem_core(pgdat->bdata, physaddr, size);
}

/* NUMA释放内存 */
void free_bootmem_node(pg_data_t *pgdat, unsigned long physaddr,
			      unsigned long size)
{
	/* 释放整页 */
	free_bootmem_core(pgdat->bdata, physaddr, size);
}

unsigned long free_all_bootmem_node(pg_data_t *pgdat)
{
	return free_all_bootmem_core(pgdat);
}

//初始化 bootmem 分配器并加入全局链表 bdata_list
unsigned long init_bootmem(unsigned long start, unsigned long pages)
{
	max_low_pfn = pages;
	min_low_pfn = start;
	//初始化 bootmem 分配器并加入全局链表 bdata_list
	return init_bootmem_core(NODE_DATA(0), start, 0, pages);
}

#ifndef CONFIG_HAVE_ARCH_BOOTMEM_NODE
void reserve_bootmem(unsigned long addr, unsigned long size)
{
	reserve_bootmem_core(NODE_DATA(0)->bdata, addr, size);
}
#endif /* !CONFIG_HAVE_ARCH_BOOTMEM_NODE */

/* UMA释放内存，参数：需要释放的内存区的起始地址和长度 */
void free_bootmem(unsigned long addr, unsigned long size)
{
	/* 释放整页 */
	free_bootmem_core(NODE_DATA(0)->bdata, addr, size);
}

//停用bootmem分配器
unsigned long free_all_bootmem(void)
{
	return free_all_bootmem_core(NODE_DATA(0));
}

void * __alloc_bootmem_nopanic(unsigned long size, unsigned long align,
				      unsigned long goal)
{
	bootmem_data_t *bdata;
	void *ptr;

	//遍历 bootmem 分配器链表头
	list_for_each_entry(bdata, &bdata_list, list) {
		ptr = __alloc_bootmem_core(bdata, size, align, goal, 0);
		if (ptr)
			return ptr;
	}
	return NULL;
}

/* 
 * size 是所需内存区的长度, 
 * align 表示数据的对齐方式 SMP_CACHE_BYTES PAGE_SIZE
 * goal 指定了开始搜索适当空闲内存区的起始地址
 * 属性( 和 __initdata )用于标记初始化函数和数据,
 * ( 和 __initdata )前缀的函数或数据在系统已经初始化之后将不再使用,只在系统初始化阶段需要
 * __initdata的使用:static char found_msg[] __initdata = "found.\n";
 * */
void * __alloc_bootmem(unsigned long size, unsigned long align,
			      unsigned long goal)
{
	/* 遍历所有的bootmem分配器,直至分配成功为止 */
	void *mem = __alloc_bootmem_nopanic(size,align,goal);

	if (mem)
		return mem;
	/*
	 * Whoops, we cannot satisfy the allocation request.
	 */
	printk(KERN_ALERT "bootmem alloc of %lu bytes failed!\n", size);
	// panic("Out of memory");
	return NULL;
}


void * __alloc_bootmem_node(pg_data_t *pgdat, unsigned long size,
				   unsigned long align, unsigned long goal)
{
	void *ptr;

	/* 尝试在该结点的bootmem分配器进行分配 */
	ptr = __alloc_bootmem_core(pgdat->bdata, size, align, goal, 0);
	if (ptr)
		return ptr;

	/* 上一步失败后,尝试所有的结点 */
	return __alloc_bootmem(size, align, goal);
}

#ifndef ARCH_LOW_ADDRESS_LIMIT
#define ARCH_LOW_ADDRESS_LIMIT	0xffffffffUL
#endif

void * __alloc_bootmem_low(unsigned long size, unsigned long align,
				  unsigned long goal)
{
	bootmem_data_t *bdata;
	void *ptr;

	list_for_each_entry(bdata, &bdata_list, list) {
		ptr = __alloc_bootmem_core(bdata, size, align, goal,
						ARCH_LOW_ADDRESS_LIMIT);
		if (ptr)
			return ptr;
	}

	/*
	 * Whoops, we cannot satisfy the allocation request.
	 */
	printk(KERN_ALERT "low bootmem alloc of %lu bytes failed!\n", size);
	// panic("Out of low memory");
	return NULL;
}

void * __alloc_bootmem_low_node(pg_data_t *pgdat, unsigned long size,
				       unsigned long align, unsigned long goal)
{
	return __alloc_bootmem_core(pgdat->bdata, size, align, goal,
				    ARCH_LOW_ADDRESS_LIMIT);
}

